Search results for "Matrix multiplication"
showing 10 items of 20 documents
Fast Approximated Discriminative Common Vectors Using Rank-One SVD Updates
2013
An efficient incremental approach to the discriminative common vector (DCV) method for dimensionality reduction and classification is presented. The proposal consists of a rank-one update along with an adaptive restriction on the rank of the null space which leads to an approximate but convenient solution. The algorithm can be implemented very efficiently in terms of matrix operations and space complexity, which enables its use in large-scale dynamic application domains. Deep comparative experimentation using publicly available high dimensional image datasets has been carried out in order to properly assess the proposed algorithm against several recent incremental formulations.
Entanglement continuous unitary transformations
2016
Continuous unitary transformations are a powerful tool to extract valuable information out of quantum many-body Hamiltonians, in which the so-called flow equation transforms the Hamiltonian to a diagonal or block-diagonal form in second quantization. Yet, one of their main challenges is how to approximate the infinitely-many coupled differential equations that are produced throughout this flow. Here we show that tensor networks offer a natural and non-perturbative truncation scheme in terms of entanglement. The corresponding scheme is called "entanglement-CUT" or eCUT. It can be used to extract the low-energy physics of quantum many-body Hamiltonians, including quasiparticle energy gaps. We…
Entanglement in Gaussian matrix-product states
2006
Gaussian matrix product states are obtained as the outputs of projection operations from an ancillary space of M infinitely entangled bonds connecting neighboring sites, applied at each of N sites of an harmonic chain. Replacing the projections by associated Gaussian states, the 'building blocks', we show that the entanglement range in translationally-invariant Gaussian matrix product states depends on how entangled the building blocks are. In particular, infinite entanglement in the building blocks produces fully symmetric Gaussian states with maximum entanglement range. From their peculiar properties of entanglement sharing, a basic difference with spin chains is revealed: Gaussian matrix…
Reverse-safe data structures for text indexing
2021
We introduce the notion of reverse-safe data structures. These are data structures that prevent the reconstruction of the data they encode (i.e., they cannot be easily reversed). A data structure D is called z-reverse-safe when there exist at least z datasets with the same set of answers as the ones stored by D. The main challenge is to ensure that D stores as many answers to useful queries as possible, is constructed efficiently, and has size close to the size of the original dataset it encodes. Given a text of length n and an integer z, we propose an algorithm which constructs a z-reverse-safe data structure that has size O(n) and answers pattern matching queries of length at most d optim…
Simulation of matrix product states for dissipation and thermalization dynamics of open quantum systems
2020
Abstract We transform the system/reservoir coupling model into a one-dimensional semi-infinite discrete chain through unitary transformation to simulate the open quantum system numerically with the help of time evolving block decimation (TEBD) algorithm. We apply the method to study the dynamics of dissipative systems. We also generate the thermal state of a multimode bath using minimally entangled typical thermal state (METTS) algorithm, and investigate the impact of the thermal bath on an empty system. For both cases, we give an extensive analysis of the impact of the modeling and simulation parameters, and compare the numerics with the analytics.
Higher order matrix differential equations with singular coefficient matrices
2015
In this article, the class of higher order linear matrix differential equations with constant coefficient matrices and stochastic process terms is studied. The coefficient of the highest order is considered to be singular; thus, rendering the response determination of such systems in a straightforward manner a difficult task. In this regard, the notion of the generalized inverse of a singular matrix is used for determining response statistics. Further, an application relevant to engineering dynamics problems is included.
Versatile Direct and Transpose Matrix Multiplication with Chained Operations: An Optimized Architecture Using Circulant Matrices
2016
With growing demands in real-time control, classification or prediction, algorithms become more complex while low power and small size devices are required. Matrix multiplication (direct or transpose) is common for such computation algorithms. In numerous algorithms, it is also required to perform matrix multiplication repeatedly, where the result of a multiplication is further multiplied again. This work describes a versatile computation procedure and architecture: one of the matrices is stored in internal memory in its circulant form, then, a sequence of direct or transpose multiplications can be performed without timing penalty. The architecture proposes a RAM-ALU block for each matrix c…
Fast Matrix Multiplication
2015
Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm running in time O(n2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078}); in particular, this approach cannot prove the conjecture that for every e > 0, …
Empirical Autotuning of Two-level Parallel Linear Algebra Routines on Large cc-NUMA Systems
2012
In large cc-NUMA systems the efficient use of the different levels of the memory hierarchy is not an easy task, and the performance of multithreading implementations of the libraries decreases when the number of cores used increases, so producing an important lost of efficiency. To alleviate this problem, routines with multilevel parallelism can be developed by combining OpenMP and BLAS parallelism. In that way, higher performance can be achieved, but it is necessary to develop some autotuning technique for the appropriate selection of the number of threads to use at each level. The selection can be made through theoretical models of the execution time or some installation methodology. This…
Response determination of linear dynamical systems with singular matrices: A polynomial matrix theory approach
2017
Abstract An approach is developed based on polynomial matrix theory for formulating the equations of motion and for determining the response of multi-degree-of-freedom (MDOF) linear dynamical systems with singular matrices and subject to linear constraints. This system modeling may appear for reasons such as utilizing redundant DOFs, and can be advantageous from a computational cost perspective, especially for complex (multi-body) systems. The herein developed approach can be construed as an alternative to the recently proposed methodology by Udwadia and coworkers, and has the significant advantage that it circumvents the use of pseudoinverses in determining the system response. In fact, ba…